Pojem a vznik kombinatoriky
Kombinatorika neboli nauka o skupinách je teorie, která se zabývá problémy s určováním počtu skupin, sestavených podle určitých pravidel z prvků dané konečné množiny.
Vznik se datuje do 17. století, kdy se hráči hazadardních her pokoušeli vypočítat pravděpodobnosti výhry v karetních hrách, kostách apod.
Základním pojmem je pojem k-tice prvků, kde k-ticí rozumíme výběr k prvků z jisté, blíže určené skupiny prvků. Vybrané prvky s v k-tici mohou, nebo nemohou opakovat. Dalším dělením je dělení na uspořádané k-tice a neuspořádané k-tice.
Základní pojmy v kombinatorice
Kombinatorické pravidlo součinu
Počet všech uspořádaných k-tic z \(n\) prvků, jejichž první člen lze vybrat právě \(n_1\) způsoby, druhý člen po výběru prvního členu právě \(n_2\) způsoby atd. až k-tý člen po výběru \((k-1)-\)ho členu právě \(n_k\) způsoby, je roven součinu \(n_1\cdot n_2\cdot\ldots\cdot n_k.\)
Variace, permutace a kombinace
Permutací bez opakování z n-prvkové množiny rozumíme každou uspořádanou n-tici prvků, vytvořenou z dané n-prvkovéé množiny tak, že každý prvek je v ní obsažen právě jednou. Počet všech takovýchto premutací je dán vzorcem:
\[P(n)=n!\]
Permutací z m-prvkové množiny \(M=\{a_1,a_2,\ldots,a_m\}\) s opakováním prvku \(a_1\) právě \(k_1\) krát, prvku \(a_2\) právě \(k_2\) krát atd., prvku \(a_m\) právě \(k_m\) krát, kde \(k_1 + k_2 + \ldots + k_m = n,\) rozumíme takovou uspořádanou n-tici, vytvořenou ze všech \(m\) prvků množiny \(M\), že se v této n-tici prvek \(a_1\) vyskytuje právě \(k_1\) krát, prvek \(a_2\) právě \(k_2\) krát atd., prvek \(a_m\) právě \(k_m\) krát. Počet všech takových permutací je dán vztahem:
\[P'_{k_1,k_2,\ldots,k_m}(n)=\frac{n!}{k_1!k_2!\cdots k_m!}.
\]
Variací k-té třídy bez opakování z n-prvkové množiny rozumíme každou uspořádanou k-tici, sestavenou z těchto prvků tak, že každý je v ní obsažen nejvýše jednou. Počet je dán vzorcem:
\[V_k(n) = \frac{n!}{(n-k)!}=n\cdot(n-1)\cdot(n-2)\cdot\ldots\cdot(n-k+1).\]
Variací k-té třídy s opakováním z n-prvkové množiny rozumíme každou uspořádanou k-tici, sestavenou pouze z těchto n prvků (prvky se v ní mohou opakovat). Jejich počet je dán vztahem:
\[V'_k(n) = n^k.\]
Kombinací k-té třídy z n-prvkové množiny bez opakování rozumíme každou neuspořádanou k-tici, sestavenou z n-prvkové množiny (každý prvek je v ní obsažen nejvýše jednou). Počet k-prvkových kombinací bez opakování je dán vztahem:
\[C_k(n)={n\choose k}.\]
Kombinací k-té třídy z n-prvkové množiny s opakováním rozumíme každou k-tici prvků této množiny takovou, že se v ní každý prvek může opakovat nejvýše k krát. Počet k-prvkových kombinací s opakováním je dán vzorcem:
\[C'_k(n) = {n+k-1\choose k}.\]
Nyní shrneme uvedené vzorce do tabulky:
|
počet skupin bez opakování |
počet skupin s opakováním |
| Variace |
\(V_k(n) = \frac{n!}{(n-k)!}.\) |
\(V'_k(n) = n^k\) |
| Permutace |
\(P(n)=n!\) |
\(P'_{k_1,k_2,\ldots,k_m}(n)=\frac{n!}{k_1!k_2!\cdots k_m!}.
\)
|
| Kombinace |
\(C_k(n)={n\choose k}.\) |
\(C'_k(n) = {n+k-1\choose k}\) |